package dicTree;

public class LongestWordInDictionary720 {
    int length = 0;
    String result = "";
    public String longestWord(String[] words) {
        TrieTree trieTree = new TrieTree();
        for (int i = 0; i < words.length; i++) {
            trieTree.add(words[i]);
        }
        trieTree.getLongestWord(0,"");
        return result;
    }


    class TrieTree {
        TrieTree[] chars = new TrieTree[26];
        boolean isEnd = false;

        public void add(String word) {
            TrieTree root = this;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (root.chars[c - 'a'] == null) {
                    root.chars[c - 'a'] = new TrieTree();
                }
                root = root.chars[c - 'a'];
            }
            root.isEnd = true;
        }

        public void getLongestWord(int depth, String cur) {
            if (depth > length) {
                length = depth;
                result = cur;
            }
            for (int i = 0; i < chars.length; i++) {
                if (chars[i] != null && chars[i].isEnd) {
                    chars[i].getLongestWord(depth + 1, cur + (char)('a' + i));
                }
            }

        }
    }

}
